package com.fmm.easy;

import java.util.ArrayList;
import java.util.List;

public class YangHuiTriangle2 {

    /**
     * @param rowIndex 杨辉三角的第几层，从 0 开始
     * @return 返回杨辉三角的第 rowIndex 行的数字
     * */
    public static List<Integer> getRow(int rowIndex) {
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i <= rowIndex; i++) {
            // 因为杨辉三角的对称性，后半部分可以直接拿前半部分计算好的值
            if (i > rowIndex / 2) {
                result.add(result.get(rowIndex - i));
            } else {
                // 求出 C(rowIndex, i) 的值，加入到 result 中
                result.add(combination(rowIndex, i));
            }
        }
        return result;
    }

    /**
     * 计算组合数
     * @param n 组合数的元素数
     * @param k 组合数的取出个数
     * @return 从 n 哥元素中取出 k 个的组合数
     * */
    public static int combination(int n, int k) {
        if (k == 0 || k == n) {
            return 1;
        }
        long result = 1;
        for (int i = 1; i <= k; i++) {
            result *= (n - k + i); // 分子部分：n * (n-1) * ... * (n-k+1)
            result /= i;           // 分母部分：k * (k-1) * ... * 1
        }
        return (int) result;
    }

    public static void main(String[] args) {
        System.out.println(getRow(30));
    }
}
